The purpose of this study is to evaluate the effectiveness of a modified form of the smallpox virus which has been manipulated to carry the gene for carcinoembryonic antigen (CEA). This molecule is expressed by a majority of adenocarcinomas of the colon. The supposition is that the immune system will respond to the vaccinia-CEA (70 Kd) vaccine causing a strong anti-CEA response similar to the anti smallpox immune response. This genetically engineered vaccine has been tested in animals and found to be safe and effective. Similar vaccination strategy has been initiated for other disease types and no unexpected reactions have been observed. This trial will evaluate the side effects as well as the response to the vaccine. The vaccination program consists of two separate vaccinations eight weeks apart. Patients will receive the first vaccination as an intradermal application of the vaccine using a standard scarification technique. They will be followed for eight weeks. If there are no side effects a booster vaccination will be admnistered. This study will be conducted on an outpatient basis.